package com.bow.algorithm.structure;

/**
 * floyd算法就是插值算法，比如0到2路径是无穷大，但插入1后，其长度就变为2了。
 * <pre>
 *    __1__2__3__4
 *  / 1  1  1  1  \
 * 0               6
 * \  5       5   /
 *  ------5-------
 * </pre>
 * distance array代表了两点之间的最短距离。
 * path array 两点之间所需要经过的点，叫做前驱矩阵。
 */
public class Floyd {


	public static void allPairsDist(int[][] a, int[][] d, int[][] path) {
		// init distance array and path array.
	    for (int i = 0; i < a.length; i++) {
			for (int j = 0; j < a.length; j++) {
				d[i][j] = a[i][j];
				path[i][j] = j;
			}
		}
		// floyd algorithm
		for (int k = 0; k < a.length; k++) {
			for (int i = 0; i < a.length; i++) {
				for (int j = 0; j < a.length; j++) {
					if (d[i][j] > d[i][k] + d[k][j]) {
						d[i][j] = d[i][k] + d[k][j];
						path[i][j] = path[i][k];
					}
				}
			}
		}
	}

	public static String printPath(int[][] path, int i, int j) {
		if (i < 0 || i > path.length - 1 || j < 0 || j > path.length - 1) {
			return null;
		}
		if (i == j) {
			return "";
		}
		if (path[i][j] == j) {
			return "";
		}
		return path[i][j] + " " + printPath(path, path[i][j], j);
	}

    /**
     * 这个方法就是让输出漂亮点，没啥意义
     * @param ary ary
     */
	private static void printArray(int[][] ary) {
		System.out.println("----0----1----2----3----4----5----6");
		for (int i = 0; i < ary.length; i++) {
            System.out.print(i+" ");
			for (int j = 0; j < ary[i].length; j++) {
				String result = null;
				if (ary[i][j] < 10) {
					result = "  " + ary[i][j];
				} else if (ary[i][j] < 100) {
					result = " " + ary[i][j];
				} else {
					result = "" + ary[i][j];
				}
				System.out.print(result + "  ");
			}
			System.out.println();
		}
	}

	public static void main(String[] args) {
		int[][] a = new int[][] {
				{ 0, 1, 100, 100, 100, 5, 100 },
				{ 1, 0, 1, 100, 100, 100, 100 },
				{ 100, 1, 0, 1, 100, 100, 100 },
				{ 100, 100, 1, 0, 1, 100, 100 },
				{ 100, 100, 100, 1, 0, 100, 1 },
				{ 5, 100, 100, 100, 100, 0, 5 },
				{ 100, 100, 100, 100, 1, 5, 0 }
		};

        int[][] d = new int[a.length][a.length];
		int[][] path = new int[a.length][a.length];
		Floyd.allPairsDist(a, d, path);
        printArray(a);
        printArray(d);
        printArray(path);
        System.out.println("---------------------------------");
        System.out.println(Floyd.printPath(path, 0, 6));
	}
}
